package lanqiaobeiGuosai.tulun;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 课程表 {
    public static void main(String[] args) {
        int[][] prerequisites = {{1,0},{0,1}};
        boolean b = canFinish(2, prerequisites);
        System.out.println(b);
    }

    /**
     * 拓扑排序 将有向无环图 按照顺序转化为线性结构的 就是拓扑排序
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表 用来保存每一个课程的先后结构 并且初始化
        ArrayList<ArrayList<Integer>> closedTable = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            closedTable.add(new ArrayList<>());
        }

        //保存入度
        int[] inDegree = new int[numCourses];

        //计算每一个的入度 同时构建一个邻接表
        for (int i = 0; i < prerequisites.length; i++) {
            int inDegreeNum = prerequisites[i][0];
            int outDegreeNum = prerequisites[i][1];
            inDegree[inDegreeNum]++;
            //添加到邻接表
            closedTable.get(outDegreeNum).add(inDegreeNum);
        }

        //用队列存储入度为0的队列 表明其是初始可选的
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        //记录已经完成的课程
        int finishCourse = 0;
        //BFS 广度搜索
        while (!queue.isEmpty()) {
            int course = queue.poll();
            finishCourse++;
            //获取当前课程的其他预先学习内容
            for (Integer i : closedTable.get(course)) {
                //当前课程完成之后 看看对应的课程是否入度为0
                inDegree[i]--;
                if (inDegree[i] == 0) {
                    //如果为0 直接添加
                    queue.add(i);
                }
            }

        }

        return finishCourse == numCourses;
    }
}
